from typing import List

"""
    给定一个不含重复数字的数组 nums ，
    返回其 所有可能的全排列 。
    你可以 按任意顺序 返回答案。

    示例 1：
            输入：nums = [1,2,3]
            输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    
    示例 2：    
            输入：nums = [0,1]
            输出：[[0,1],[1,0]]
"""
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        tem = []
        used = []
        for i in range(len(nums)):
            used.append(0)

        def backtracking(height):
            if height == len(nums):
                ans.append(tem.copy())
            for i in range(0,len(nums)):
                if used[i] == 1:
                    continue
                tem.append(nums[i])
                used[i] = 1
                backtracking(height+1)
                tem.pop()
                used[i] = 0
            return
        backtracking(0)
        return ans